package week_six;

public class JumpGame_55 {
    public boolean canJump(int[] nums) {
        //DP， 动规实现
        int length = nums.length;
        boolean[] reach = new boolean[length];
        reach[0] = true;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (reach[j] && j + nums[j] >= i) {
                    // System.out.println("reach "+ i);
                    reach[i] = true;
                }
            }
        }

        return reach[length - 1];
    }

    public boolean canJump1(int[] nums) {
        //贪心，往后多看一步
        //下一步能跳的最远的位置就是当前最优解。
        int ans = 0;
        int length = nums.length;
        int max = 0;
        int next = 0;

        for (int i = 0; i < length - 1; i++) {
            max = Math.max(max, i + nums[i]);
            if (max == i) return false;
        }
        return max >= length - 1;
    }
}
